package week10;

import java.util.*;

/**
 *
 * 699. 掉落的方块
 * https://leetcode-cn.com/problems/falling-squares/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：23 ms, 在所有 Java 提交中击败了17.35% 的用户
 * 内存消耗：39.3 MB, 在所有 Java 提交中击败了46.94% 的用户
 * 通过测试用例：44 / 44
 * 炫耀一下:
 *
 *
 */
public class Week10FallingSquares {

    public List<Integer> fallingSquares(int[][] positions) {
        Set<Integer> coordsSet = new HashSet<Integer>();
        for(int[] position : positions) {
            coordsSet.add(position[0]);
            coordsSet.add(position[0] + position[1] - 1);
        }
        List<Integer> coordsList = new ArrayList(coordsSet);
        Collections.sort(coordsList);

        Map<Integer, Integer> index = new HashMap<Integer, Integer>();
        int t = 0;
        for(int coord : coordsList) {
            index.put(coord, t++);
        }

        SegmentTree segmentTree = new SegmentTree(coordsList.size());
        int best = 0;
        List<Integer> resultList = new ArrayList<Integer>();
        for(int[] position : positions) {
            int left = index.get(position[0]);
            int right = index.get(position[0] + position[1] - 1);
            int high = segmentTree.query(left, right) + position[1];
            segmentTree.update(left, right, high);
            best = Math.max(best, high);
            resultList.add(best);
        }

        return resultList;
    }

}

class SegmentTree {
    int n;
    int h;
    int[] tree;
    int[] lazy;

    public SegmentTree(int n) {
        this.n = n;
        h = 1;
        for (; (1 << h) < n; ) {
            h++;
        }
        tree = new int[n * 2];
        lazy = new int[n];
    }

    private void apply(int x, int val) {
        tree[x] = Math.max(tree[x], val);
        if (x < n) {
            lazy[x] = Math.max(lazy[x], val);
        }
    }

    private void pull(int x) {
        for (; x > 1; ) {
            x >>= 1;
            tree[x] = Math.max(tree[x * 2], tree[x * 2 + 1]);
            tree[x] = Math.max(tree[x], lazy[x]);
        }
    }

    private void push(int x) {
        for (int size = h; size > 0; size--) {
            int y = x >> size;
            if (lazy[y] > 0) {
                apply(y * 2, lazy[y]);
                apply(y * 2 + 1, lazy[y]);
                lazy[y] = 0;
            }
        }
    }

    public void update(int left, int right, int high) {
        left += n;
        right += n;
        int leftSize = left;
        int rightSize = right;
        for (; left <= right; ) {
            if ((left & 1) == 1) {
                apply(left++, high);
            }
            if ((right & 1) == 0) {
                apply(right--, high);
            }
            left >>= 1;
            right >>= 1;
            pull(leftSize);
            pull(rightSize);
        }

    }

    public int query(int left, int right) {
        left += n;
        right += n;
        int result = 0;
        push(left);
        push(right);
        for (; left <= right; ) {
            if ((left & 1) == 1) {
                result = Math.max(result, tree[left++]);
            }
            if ((right & 1) == 0) {
                result = Math.max(result, tree[right--]);
            }
            left >>= 1;
            right >>= 1;
        }
        return result;
    }
}
